

lst = [89, 92, 39, 66, 100, 101, 29, 98]
# 从小到大排序
# 归并排序

def func_sort(lst):
    if len(lst)>1:
        mid = len(lst)//2
        left = func_sort(lst[:mid])
        right = func_sort(lst[mid:])
        return merge(left, right)
    else:
        return lst

def merge(left, right):
    lst = []
    while len(left) > 0 and len(right)>0:
        if left[0] > right[0]:
            lst.append(right.pop(0))
        else:
            lst.append(left.pop(0))
    if left:
        lst+=left
    if right:
        lst +=right
    return lst


print(func_sort(lst))
